Standards have been proposed by a study group of the CCITT to achieve some compatibility among the digital facsimile equipments that are linked through telephone networks. The objective is to transmit an A4 document, about 81/2 by 12 inches, over a telephone line in one minute, using 1728 pels per line and 1188 lines per page. This amounts to 2,052,864 pels per page, requiring a transmission rate of 34.2 kilobits/second.
The present 9600 baud maximum feasible transmission rate over telephone lines is equal to 9.6 kilobits/second, using non-return-to-zero coding. Therefore, a page would require 7 minutes, 8 seconds for transmission. A resolution of 3.85 lines per mm is approximately 100 lines per inch. High resolution facsimile uses higher resolution, averaging about 203 lines per inch which is approximately a horizontal resolution of 8 pels/mm. An 81/2.times.11 inch document having a resolution of 8 pels/mm in both dimensions contains 3,860,637 pels. At 4.8 kilobits/second, 13.5 minutes would be required to transmit a page.
To reduce transmission times, data is compressed, i.e., the number of bits required to convey the information is reduced with no significant loss of information. This is possible because of the redundant information previously described.
Data can be reduced by taking advantage of statistical relationships, which is another type of redundancy. For example, some letters occur more often than others. In English, for example, E occurs most frequently, followed in order of frequency by T, O, A, N, I, R, S, C, H and so on. To encode all the letters, numerals, and punctuation marks requires six bits per character. Taking advantage of the knowledge of this frequency, fewer bits are assigned to represent E than to represent Z or Q, relatively infrequent letters. The sequences of bits must be unique so that no bit combination of two frequent letters is the same code as that for an infrequent letters. Consider the following assignment:
______________________________________ E 00 I 1011 T 01 R 1100 O 1000 S 1101 A 1001 C 1110 N 1010 H 11110 ______________________________________
Sending THE SCORE IS A TIE using 6 bits per character (and ignoring spaces) requires 84 bits. Using the above assignment, only 47 bits are required. The beginning is 01111100011011110 . . . . The first two elements are recognized as T. The next sequence of four ones eliminates all but H which is identified by the following zero. It is easily verified that no ambiguity exists even though fewer than half the number of bits is required to encode the message. Such codes are called variable length codes or Huffman codes. The Morse code is an example of such a code and exhibits a high inverse coefficient of correlation between letter frequency and the time required for transmission.
In facsimile transmission, however, individual letters are not considered, only sequences usually of black and white spots as pels (picture elements). These sequences are encoded as series of logical ones and zeros. Viewed as a Markov chain, the series leads to the idea of run-length coding. (Being of Markov chain merely denotes that the probability of a white pel or black pel occurring is not independent from the preceding pels). Run length coding uses a code to represent the number of pels in a sequence of the same color. For example, a sequence of 100 white pels, instead of being transmitted as 100 zeros, is transmitted as a code indicating the color followed by a code indicating 100. Alternatively, the numbers only need be used, the color alternating for each number. Significantly fewer bits are required.
A refinement combines the above two techniques. The statistical relationships underlying the frequency distribution of certain run lengths can be used to assign variable length codes. This is a popular coding scheme, known as a one-dimensional Huffman run-length encoding. The code usually used is a modified Huffman code. This scheme provides efficient compression, typically providing compression ratios between 6 and 22 depending on the source documents.
U.S. Pat. No. 4,091,424 discloses another prior art approach to data compression that is apparently useful with printed text. The principle is to enclose each character with the smallest possible rectangle. The data in the rectangle is then encoded and transmitted with information identifying the coordinates of the initial pel of the character and the size of the rectangle. At the receiving end, the encoded data is used to reconstruct the character in the position indicated by the coordinate and size information. Further compression is achieved by maintaining a library of characters at both the receive and transmit ends. If a character matches one in the library, only an identifier is sent with the coordinate information, reducing the amount of information required to be transmitted. The method shown in the patent is restricted to printed text and requires storing a full page at both the transmit and the receive ends.
The present invention, by transmitting the residual information remaining after a recognized figure is erased, can be used for all printed or pictorial information.
Other prior art systems increase their compression ratios by combining or skipping alternate lines. Prior art references representative of this approach include U.S. Pat. No. 4,291,339 (Ogawa et al.) and "Picture Restoration Algorithm for Facsimile Machines," K. Y. Wong, IBM Technical Disclosure Bulletin, Vol. 19, No. 2, July 1976, pp. 668-671. Since the present invention operates on each individual line, this prior art is not further discussed.
Background material useful for understanding the present state of the art includes "A Means for Achieving a High Degree of Compaction on Scan-Digitized Printed Text," R. N. Ascher and George Nagy, IEEE Transactions on Computers, Vol. C-23, No. 11, November 1974, pp. 1174-1179; U.S. Pat. Nos. 4,191,974 (Ono et at.); and 3,980,809 (Cook).
Run-length encoding schemes are described in U.S. Pat. Nos. 3,883,847 and 4,103,287; "High Fidelity Encoding of Two-Level, High Resolution Images," A. J. Frank, IEEE Int'l Conf. on Communications, June 1973, pp. 26-5 to 26-11; "International Digital Facsimile Coding Standards," Roy Hunter and A. Harry Robinson, Proceedings of the IEEE, Vol. 68, No. 7, July 1980, pp. 854-867; "Two-Dimensional Facsimile Coding Scheme," Joan L. Mitchell and Gerald Goertzel, ICC 1979 Conference Record, 8.7.1-8.7.5; "Proposed Addition to Draft Recommendation T.4--Standardization of Group 3 Facsimile Apparatus for Document Transmission," CCITT Study Group XIV, Kyoto, Nov. 7-15, 1979 (Temporary Document No. 39-E); "Facsimile Image Coding," Joan L. Mitchell, AFIPS Conference Proceedings, Vol. 49, National Computer Conference 1980, pp. 423-426; "Recent Advances in Data-Conversion Facsimile Techniques," W. B. Pennebaker, G. Goertzel, and J. L. Mitchell, Journal of Applied Photographic Engineering, Vol. 6, No. 4, August 1980, pp. 93-96.